public class BubbleSort {
/*    时间复杂度：
    最坏情况下（数组完全逆序），时间复杂度为 O(n²)。
    最好情况下（数组已经有序），时间复杂度为 O(n)。
    空间复杂度：
    冒泡排序是原地排序算法，空间复杂度为 O(1)*/
// 冒泡排序算法实现:升序排序
    public static void bubbleSort1(int[] arr) {
        int len = arr.length;
        boolean flag;
        for (int i=0; i<=arr.length - 1;i++){
            flag = false;
            for (int j= 0; j< arr.length -1; j++){
                if (arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
    // 冒泡排序算法实现:降序排序
    public static void bubbleSort2(int[] arr) {
        int len = arr.length;
        boolean flag;
        for (int i=0; i<=arr.length - 1;i++){
            flag = false;
            for (int j= 0; j< arr.length -1; j++){
                if (arr[j]<arr[j+1]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 6, 7, 8, 9};
        System.out.println("排序前的数组:");
        printArray(arr);

        bubbleSort1(arr);
       // bubbleSort2(arr);
        System.out.println("排序后的数组:");
        printArray(arr);
    }
}
